#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/21 15:23
# ===========================================
#       题目名称： 18. 四数之和
#       题目地址： https://leetcode.cn/problems/4sum/description/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================


class Solution:
    """
        实现思路：
            1、排序一下
            2、删除超过3个相同的普通数值 和 超过4个为0的元素
            3、循环求值

    """

    def fourSum(self, nums, target):
        # 排序
        nums.sort()
        # 删除多余数据
        cur_index = 3
        while cur_index < len(nums):
            if nums.count(nums[cur_index]) > 4:
                del nums[cur_index]
            else:
                cur_index += 1
        # 定义返回值
        res = set()
        # 找到4数之和 0 1 2 3 4
        for i in range(len(nums) - 3):
            for j in range(i + 1, len(nums) - 2):
                for k in range(j + 1, len(nums) - 1):
                    for l in range(k + 1, len(nums)):
                        # print(i, j, k, l)
                        tmp = nums[i] + nums[j] + nums[k] + nums[l]
                        if target < tmp:  # 核心提速代码
                            break
                        if target == tmp:
                            res.add((nums[i], nums[j], nums[k], nums[l]))
                            break
        return list([list(res) for res in res])


if __name__ == '__main__':
    s = Solution()
    print("nums = [1,0,-1,0,-2,2], target = 0 =>" + str(
        s.fourSum(nums=[1, 0, -1, 0, -2, 2], target=0)))  # [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
    print("nums = [2,2,2,2,2], target = 8 =>" + str(s.fourSum(nums=[2, 2, 2, 2, 2], target=8)))  # [[2,2,2,2]]
    print("nums = [-1,0,1,2,-1,-4], target = -1 =>" + str(
        s.fourSum(nums=[-1, 0, 1, 2, -1, -4], target=-1)))  # [[-4,0,1,2],[-1,-1,0,1]]
    print("nums = [0,0,0,0], target = 0 =>" + str(
        s.fourSum(nums=[0, 0, 0, 0], target=0)))  # [[0,0,0,0]]
    print(s.fourSum([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 8))
